package wtx.leetcode;

class BetterSolution {
  public int search(int[] nums, int target) {
      if(nums == null || nums.length == 0) return -1;
      int ret = -1;
      int left = 0;
      int right = nums.length - 1;
      int mid = -1;
      int leftEnd = nums[0];
      int rightEnd = nums[nums.length - 1];
      while(left <= right){
          mid = left + (right - left) / 2;
          if(nums[mid] == target){
              ret = mid;
              break;
          }else if(nums[mid] >= leftEnd){
              //On the upper half
              if(target >= nums[left] && target < nums[mid]){
                  right = mid - 1;
              }else left = mid + 1;
          }else{
              //On the lower half
              if(target > nums[mid] && target <= rightEnd ){
                  left = mid + 1;
              }else right = mid - 1;
          }
      }
      return ret;
  }
}